class Solution {
    public String[] digits;
    public int dp[];

    public int atMostNGivenDigitSet(String[] digits, int n) {
    this.digits = digits;
    char[] s = Integer.toString(n).toCharArray(); 
    dp = new int[s.length];
    Arrays.fill(this.dp,-1);
    return dfs(0,s,true,false);
    }


    public int dfs(int i,char[] s,boolean is_limit,boolean is_num)
    {
        if(i==s.length)
        {
            return is_num?1:0;
        }
        var res =0;
        if(!is_num) res = dfs(i+1,s,false,false);
        if(!is_limit&&is_num&&dp[i]>=0)
        {
            return dp[i];
        }
        var up = is_limit?s[i]:'9';
        for(var d:digits)
        {
           if(d.charAt(0)>up) break;
           res+=dfs(i+1,s,is_limit&&d.charAt(0)==up,true);
        }
        if(!is_limit&&is_num) dp[i] = res;
        return res;
    }
}